package com.ls.que86_90;

/**
 * @author ：ls
 * @date ：2022/3/8 9:42
 * @description：...
 */
public class IsScramble {
    public boolean isScramble(String s1, String s2) {
        if (s1.length()!=s2.length())
            return false;
        int n = s1.length();
        boolean[][][] dp = new boolean[n][n][n+1];

        // 初始化单个字符
        int i,j,k,len;
        for (i=0;i<n;i++){
            for (j=0;j<n;j++){
                if (s1.charAt(i) == s2.charAt(j)){
                    dp[i][j][1] = true;
                }
            }
        }

        // 动态规划
        for (len=2; len<=n;len++){
            for (i=0;i<=n-len;i++){
                for (j=0;j<=n-len;j++){
                    for (k=1; k<=len-1;k++){
                        if (dp[i][j][k] && dp[i+k][j+k][len-k] || dp[i][j+len-k][k] && dp[i+k][j][len-k]){
                            dp[i][j][len] = true;
                            break;
                        }
                    }
                }
            }
        }
        return dp[0][0][n];
    }
}
